import numpy as np                        #导入相关库
import matplotlib.pyplot as plt
from statistics import mean
from collections import Counter

####################################################################################################
# 定义两点分布的类，用于制作特定序列的0，1列表
class bernoulli():
    def pmf(x, p):  # 两点分布的概率函数
        f = p ** x * (1 - p) ** (1 - x)
        return f

    def rvs(p, size):
        rvs = np.array([])
        #print(type(size))
        for i in range(0,size):
            if np.random.rand() <= p:
                a = 1
                rvs = np.append(rvs, a)
            else:
                a = 0
                rvs = np.append(rvs, a)
        return rvs

##############################################################################################################
#定义一个深度优先查询矩阵团簇的类
class solution:
    def __init__(self, im):
        self.im = im
        m, n = im.shape
        self.mask = [[0 for _ in range(n)] for _ in range(m)]

    def isValid(self, i, j, mask, im):
        m, n = im.shape
        return i >= 0 and i < m and j >= 0 and j < n and mask[i][j] == 0 and im[i][j] == 1

    def add(self, i, j, mask, im, q):
        if self.isValid(i, j, mask, im):
            q.append([i, j])
            self.mask[i][j] = 1

    def bsfsolver(self):
        m, n = self.im.shape
        res = []
        for i in range(m):
            for j in range(n):
                if self.mask[i][j] == 1 or self.im[i][j] == 0:
                    continue
                P, Q = list(), list()
                P.append([i, j])
                self.mask[i][j] = 1
                while P:
                    temp = P.pop(0)
                    Q.append(temp)
                    self.add(temp[0] - 1, temp[1], self.mask, im, P)
                    self.add(temp[0] + 1, temp[1], self.mask, im, P)
                    self.add(temp[0], temp[1] - 1, self.mask, im, P)
                    self.add(temp[0], temp[1] + 1, self.mask, im, P)
                res.append(Q)
        return res

#######################################################################################################################

#定义一个计数函数，用于统计在各个概率值下矩阵中各个团簇的大小，并存于列表cluster_count_list中
def cluster_count_list(res):
    cluster_count1=[]
    for a in res:
        cluster_count1.append(len(a))
    return cluster_count1


#定义一个画图函数，用于绘制最大，次大，平均团簇随概率的变化
def hua_tu(max_X,max_X1,mean_X,a):
    plt.title('团簇大小随概率的变化')  # 折线图标题
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 显示汉字
    plt.xlabel('概率值')  # x轴标题
    plt.ylabel('团簇大小')  # y轴标题
    plt.plot(a, max_X, marker='o', markersize=3)  # 绘制折线图，添加数据点，设置点的大小
    plt.plot(a, max_X1, marker='o', markersize=3)
    plt.plot(a, mean_X, marker='o', markersize=3)
    plt.legend(['最大值', '次大值','平均值'])  # 设置折线名称
    plt.show()



m=150                 #矩阵的维度
n=150
a = np.arange(0.01, 1, 0.01)         #概率变化的步长
max_X = []                        #存储各个概率值下最大团簇的大小
max_X1 = []                       #存储各个概率值下次大团簇的大小
mean_X = []                       ##存储各个概率值下平均团簇的大小

for p in a:                                 #循环0~1概率值
    records = bernoulli.rvs(p, size=m * n) #调用两点分布的类形成0~1列表
    im = np.array(records).reshape(m, n)    #将0~1列表转换为矩阵（二维数组）
    s = solution(im)
    res = s.bsfsolver()                     #调用深度优先类查询矩阵的团簇
    list1 = cluster_count_list(res)           #调用计数函数
    result = Counter(list1)                 #各个团簇值计数
    print(result)


    if len(list1):
        max_X.append(max(list1))
        mean_X.append(mean(list1))
        list1.remove(max(list1))
        if len(list1):
            max_X1.append(max(list1))
        else:
            max_X1.append(0)
    else:
        max_X.append(0)
        max_X1.append(0)
        mean_X.append(0)


    max_res_index = res.index(max(res, key=len))

    for m1 in res[max_res_index]:
        im[m1[0]][m1[1]] = 2  # 删除最大团簇，方便寻找次大团簇

    middle = res[max_res_index]
    res.remove(res[max_res_index])
    # 寻找次大团簇并改变次大团簇的值，方便作图
    if res == []:
        second_res_index = 0
    else:
        second_res_index = res.index(max(res, key=len))
        for m1 in res[second_res_index]:
            im[m1[0]][m1[1]] = 3

    # 将最大团簇的值加回去
    res.append(middle)
    plt.imshow(im)
    #plt.savefig('C:\\save\\save{}.png'.format(m1))
    plt.pause(0.01)

    #plt.show()
    #plt.clf()
plt.ioff()      #关闭interactive mode
plt.show()      #显示图像1,2并且阻塞程序
hua_tu(max_X, max_X1, mean_X, a)
